package com.xinwei.leetcode.数组;
// https://leetcode-cn.com/problems/sort-an-array/

import com.sun.javafx.image.IntPixelGetter;
import com.sun.org.apache.xerces.internal.impl.dv.dtd.XML11IDDatatypeValidator;
import com.sun.org.apache.xml.internal.utils.ObjectVector;
import com.xinwei.linearExercise.ArrayList;

// 数组索引的设计最好都是左闭右开，这样右减左就是元素数量
public class _912_排序数组 {
    // 冒泡
    public static int[] sortArray(int[] nums) {
        int t = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    t = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = t;
                }
            }
        }
        return nums;
    }

    /**
     * 插入排序
     */
    public static int[] sortArray1(int[] nums) {
        for (int i = 1; i < nums.length; i++) { // 这里i相当于未排序的数的第一个，可以默认第一张牌是排序好的，所以起始为1
            int cur = i;
            while (cur > 0 && (nums[cur] - nums[cur - 1]) < 0) {
                swap(nums, cur, cur - 1);
                cur --;
            }
        }
        return nums;
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }


    /**
     * 利用二分搜索优化插入排序
     */
    public static int[] sortArray2(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int insertIndex = search(i, nums);
            for (int j = i; j > insertIndex; j--) {
                nums[j] = nums[j - 1];
            }
            nums[insertIndex] = num;
        }
        return nums;
    }

    // 用二分搜索找到 index 位置元素的待插入位置
        // 为什么参数是索引而不是值，因为 index == end 包含了已排好序的数组的范围
    private static int search(int index, int[] nums) {
        int begin = 0;
        int end = index;
        int mid = 0;
        while (begin < end) {
            mid = (begin + end) >> 1;
            if (nums[index] < nums[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }


    /**
     * 归并排序
     */
    static int[] leftNums;

    public static int[] sortArray3(int[] nums) {
        int capacity = nums.length >> 1;
        leftNums = new int[capacity];
        sort(nums, 0, nums.length);
        return nums;
    }

    private static void sort(int[] nums, int begin, int end) {
        if (end - begin < 2) return;
        int mid = (begin + end) >> 1;
        sort(nums, begin, mid);
        sort(nums, mid, end);
        merge(nums, begin, mid, end);
    }


    private static void merge(int[] nums, int begin, int mid, int end) {
        int li = 0, le = mid - begin; // li用来记录左边正在比较的值，le左边的边界
        int ri = mid, re = end; // ri用来记录右边正在比较的值，re右边的边界
        int ai = begin; // ai用来记录正在覆盖的值
        for (int i = li; i < le; i++) {
            leftNums[i] = nums[begin + i]; // 这里备份左边数组的开头未必是零，要注意
        }
        while (li < le) { // 只要左边没完，就得继续判断
            if (ri < re && leftNums[li] > nums[ri]) { // 反过来小于等于，这样才能保证稳定性 ,同时 ri < re 保证了数组不越界
                nums[ai++] = nums[ri++];
            } else {
                nums[ai++] = leftNums[li++];
            }
        }
    }


    /**
     * 快速排序
     */
    public static int[] sortArray4(int[] nums) {
        sort1(nums, 0, nums.length);
        return nums;
    }

    // 对 begin 到 end 范围内的元素进行快速排序
    private static void sort1(int[] nums, int begin, int end){
        if (end - begin < 2) return;
        // 找到轴点
        int pivotIndex = pivotIndex(nums, begin, end);
        // 对子序列进行快速排序
        sort1(nums, begin, pivotIndex);
        sort1(nums, pivotIndex + 1, end);
    }

    // 构造出 [begin, end) 范围的轴点元素
    private static int pivotIndex(int[] nums, int begin, int end){
        swap(nums, begin, (int) (begin + Math.random() * (end - begin)));
        // 备份轴点元素
        int pivot = nums[begin];
        // 使 end 指向最后一个元素
        end--;

        // 这里非常巧妙的设计思路，巧妙利用三个条件一样 while 循环让代码交替执行
        while (begin < end) {
            while (begin < end) {
                if (nums[end] > pivot) {
                    end--;
                }else {
                    nums[begin++] = nums[end];
                    break;
                }
            }

            while (begin < end) {
                if (nums[begin] < pivot) {
                    begin++;
                }else {
                    nums[end--] = nums[begin];
                    break;
                }
            }
        }

        // 最后 begin == end
        nums[begin] = pivot;
        return begin;
    }
}
